The present invention is directed to methods for synthesizing balanced clock trees for an integrated circuit design. More specifically, but without limitation thereto, the present invention is directed to distributing a clock signal uniformly over a clock cycle to reduce peak current demand for an array of memory circuits without affecting timing, that is without increasing the worst path delay.
As the number of memories increases in integrated circuit designs, the problem of instantaneous peak current becomes increasingly important. Voltage drop due to the peak current demand from simultaneous switching of a large number of memory devices can result in a malfunction in the operation of the integrated circuit.
In one aspect of the present invention, a method of calculating skews for memory cells and flip-flops in a circuit design to reduce peak power includes receiving a circuit design containing memory cells and other clocked cells; constructing a first graph that includes a union of all inputs, vertices representative of the memory cells and the other clocked cells, a union of all outputs, and edges between the vertices each having a length equal to a delay between corresponding vertices minus a clock period; constructing a second graph having vertices representative of only the memory cells and corresponding edges such that the maximum length between any two corresponding vertices is less than zero; calculating a skew for each of the memory cells from the second graph; constructing a third graph from the first graph by merging the vertices of the memory cells into a single vertex; calculating a skew for each of the other clocked cells from the third graph; normalizing each skew calculated for the other clocked cells; recalculating the skew for each of the memory cells from the normalized skew calculated for the other clocked cells; and generating as output the recalculated skew for each of the memory cells.
In one embodiment, the function of calculating a first skew for each of the memory cells includes:
constructing a sequence i0, i1, . . . , im wherein i0 equals zero and an index ik+1=i has a value such that ƒ(Mik+1) less than E*(k+1) wherein ƒ(Mi)=min(t*E+MR(Mit, Mi), t=0,1, . . . , k), MR(Mi, Mj) equals a negative of the length of the edge from vertex Vj to Vi, E is a constant greater than zero, m is a positive integer, and k is an integer between 0 and m;
finding a length R(V,MM) of an edge (V,MM) incident to a vertex MM in the third graph;
defining a skew assigned to a vertex V of the third graph on the t-th iteration as SQ(t, V) and setting SQ(0, V) equal to zero for all vertices V of the graph FG;
selecting a vertex V from the third graph having the edges (V0, V), (V1, V), . . . , (Vk, V);
defining a function EST(t, V) as the maximum value of the sequence SQ(t, Vi)+R(Vi,V), i=0,1, . . . , k; and
calculating a skew for each of the clocked non-memory cells from the function EST(t, V).
In another embodiment, the skew SQ(t+1, V) is calculated substantially from
if SQ(t,V) less than EST(t,V), then SQ(t+1,V)=EST(t,V)
otherwise, SQ(t+1,V)=SQ(t,V)
until SQ(t+1, V) is equal to SQ(t, V) for all vertices V in the third graph.
In another embodiment, the skews SQit for the memory cells are calculated substantially according to SQit=E*t, t=0,1, . . . , m.
In another embodiment, the length R(V,MM) is the maximum value of the series R(V, Mit)xe2x88x92SQit, t=0,1, . . . , k.
In another embodiment, the skews of the clocked non-memory cells are normalized by subtracting a ports skew from each of the skews of the other clocked cells.